package com.example.leetcode.prcatice;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。
 *
 * 给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。
 *
 * 题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。
 *
 * 返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test1473 {

    public int[] restoreArray(int[][] adjacentPairs) {
        int len = adjacentPairs.length;
        int[] result = new int[len+1];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] is:adjacentPairs) {
            map.putIfAbsent(is[0],new ArrayList<>());   //key不存在就插入
            map.putIfAbsent(is[1],new ArrayList<>());
            map.get(is[0]).add(is[1]);
            map.get(is[1]).add(is[0]);
        }
        for (Map.Entry<Integer,List<Integer>> entry:map.entrySet()) {
            Integer key = entry.getKey();
            List<Integer> value = entry.getValue();
            if(value.size() ==1){
                result[0] = key;
                break;
            }
        }
        result[1] = map.get(result[0]).get(0);
        for (int i = 2;i<len+1;i++){
            List<Integer> adj = map.get(result[i - 1]);
            result[i] = result[i-2] == adj.get(0)? adj.get(1):adj.get(0);
        }
        return result;
    }
}
